package com.ys.p2LinkedList模拟实现;

/**
 * 描述: 模拟实现LinkedList
 * 底层: 采用双链表
 * 操作; 首要操作: 把元素封装成节点对象
 * 双链表的数据结构特点:
 *  fastNode 的 prev = null
 *  lastNode 的 next = null
 * @author CodeYang
 * @version 2020/12/25 19:32
 */
public class LinkedList<E>  implements List<E>{
    /**
     *  双链表的首节点
     */
    private Node<E> fastNode;
    /**
     *  双链表的尾节点
     */
    private Node<E> lastNode;
    /**
     *  存储元素的实际个数
     */
    private int size;

    /**
     * 获得元素的实际个数
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 添加元素，在List末尾添加元素
     *
     * @param element 需要插入元素
     */
    @Override
    public void add(E element) {
        // 1 元素封装成节点对象
        Node<E> eNode = new Node<E>(element);
        // 2 把节点对象添加进入双链表
        // 3 判断双链表是否存在: 判断首节点是否为null
        if (fastNode == null){
            // 如果双链表不存在,则把 元素节点 设为 双链表的首节点
           // fastNode = lastNode =eNode;
             fastNode  =eNode;
            //都要指向 lastNode = eNode 我们提到外面去
        } else {
            // 双链表存在,则把节点添加到 双链表的尾部
            //  双链表的添加元素到尾部的步骤:
            //  一: 让 尾节点的next -> eNode
            lastNode.next = eNode;
            //  二: eNode.prev -> lastNode
            eNode.prev = lastNode;
            //  三 : 更新尾节点 lastNode = eNode
           // lastNode = eNode;
        }
        lastNode = eNode;
        // 添加元素后  更新size
        size++;

    }

    /**
     * 插入元素，在指定索引位置插入元素
     *  插入元素的取值范围为: [0,size]
     * @param index   需要插入的索引位置
     * @param element 需要插入元素
     */
    @Override
    public void add(int index, E element) {
        // 判断范围合法
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("序号越界异常:index:"+index);
        }
        // 封装元素成节点对象
        Node<E> eNode = new Node<>(element);
        // 处理插入序号在开头的情况
        if (index == 0){
            // 处理当前节点与首节点的关系,并更新其为首节点
            eNode.next = fastNode;
            fastNode.prev = eNode;
            fastNode = eNode;
        } else if (index == size){
            // 处理 插入序号在双链表结尾情况
            eNode.prev = lastNode;
            lastNode.next = eNode;
            lastNode = eNode;
        } else {
            // 处理插入序号 在 中间情况 处理 前一个节点 当前节点 后一个节点之间的指向关系
            Node<E> preNode = findNode(index -1);
            // 这里还没肢解原理的指向关系,所以
            // Node<E> nextNode =findNode(index); 也可以这样,但是这样浪费效率
            Node<E> nextNode = preNode.next;
            // 设置 封装节点与 preNode之间的关系
            preNode.next = eNode;
            eNode.prev = preNode;
            // 设置 节点对象 与nextNode 之间的关系
            nextNode.prev = eNode;
            eNode.next = nextNode;
        }
        // 插入成功 更新size
        size++;

    }

    /**
     * 根据索引删除数组元素
     *
     * @param index 删除元素的索引
     * @return 返回被删除的元素
     */
    @Override
    public E remove(int index) {
        // [0,size-1]
        checkIndexOutBuns(index);
        // 定义一个变量用于保存要删除的节点元素
        E oldValue = null;
        if (index == 0){
            // 要删除节点在开头
            //获得首节点后面的一个节点
            Node<E> nextNode = fastNode.next;
            // 处理 这个 nextNode 与  fastNode 之间的关系
            if (nextNode != null){
                // 首节点的特点:
                nextNode.prev =null;
            }
            fastNode.next =null;
            // 获得节点元素的内容
            oldValue = fastNode.element;
            fastNode = nextNode;
        }else if (index == size-1){
            // 获得尾节点的前一个节点
            Node<E> preNode = lastNode.prev;
            // 取消 指向
            preNode.next = null;
            lastNode.prev = null;
            oldValue = lastNode.element;
            // 更新尾节点: 向前移
            lastNode = preNode;

        }else {
            // 处理删除元素在中间
            // 前一个节点;
            Node<E>  preNode = findNode(index-1);
            // 当前节点:
            Node<E> currNode = preNode.next;
            // 下一个节点;
            Node<E> nextNode = currNode.next;

            // 处理 三个节点之间的关系
            preNode.next = nextNode;
            nextNode.prev = preNode;
            currNode.prev =null;
            currNode.next =null;
            oldValue = currNode.element;
            currNode.element =null; // GC 回收


        }
        // 更新关系之后做size更新
        size--;
        return oldValue;
    }

    /**
     * 根据参数来删除数组元素
     *
     * @param element 需要删除的元素
     * @return 返回是否删除成功
     */
    @Override
    public boolean remove(E element) {


        return false;
    }

    /**
     * 根据索引获取元素
     * index 的元素取值范围: [0,size -1]
     * @param index 获取元素的索引值
     * @return 返回index对应的元素值
     */
    @Override
    public E get(int index) {
        // index 是否合法
        checkIndexOutBuns(index);
        return findNode(index).element ;
    }

    /**
     *  判断序号范围是否合法 [0,size-1]
     * @param index
     */
    private void checkIndexOutBuns(int index){
        if (index < 0 || index >= size){
            throw new IndexOutOfBoundsException("序号越界异常:index:"+index);
        }
    }

    /**
     * 根据序号 查找双链表的中的Node节点
     * 查找方式: 两种情况:
     * 1 : 查找元素在左半区 [0,size/2) 从前往后查
     * 2 : 查找元素在右半区 [size/2, size-1 ]  从后往前查
     * @param index
     * @return 返回 index 对应的节点对象
     */
    private Node<E> findNode(int index){
        // 到这里了index 肯定已经在合法范围了
        // (size>>1) 等价于 size/2 情况一
        if (index < (size>>1)){
            // 遍历双链表: 从前往后查找,要先定义一个临时节点用于链表的辅助遍历
            Node<E> tempNode = fastNode;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
            // 返回 index 对应的
            return tempNode;
        } else {
            // 情况2
            Node<E> tempNode = lastNode;
            // 分析 双链表从后往前查找的特点: 发现循环(查找)的的次数应为 size - index -1
            for (int i = 0; i < size - index - 1; i++) {
                    // 从后往前
                    tempNode = tempNode.prev;
            }
            return tempNode;
        }

    }

    /**
     * 判断集合是否为空
     *
     * @return 如果集合为空，则返回true；如果集合不为空，则返回false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回第一次出现在集合中的索引位置（从前往后找）
     *
     * @param element 需要查找的元素
     * @return 如果element在数组中存在，则返回第一次出现的索引位置；如果element在数组中不存在，则返回-1.
     */
    @Override
    public int indexOf(E element) {
        return 0;
    }

    /**
     *  双链表的节点类:
     *  private : 因为只有本类使用,不需要暴露给其他类
     *  static : 这样在外部类加载时 可以直接加载子类(节点类)
     *   双向连标签的 的数据模型:
     *    [ pre | data | next]
     * @param <E>
     */
    private static class Node<E>{
        /**
         * 存储上一个节点的地址在
         */
        private  Node<E> prev;
        /**
         * 存储下一个节点的地址值
         */
        private  Node<E> next;

        /**
         * 元素内容
         */
        private  E element;

        /**
         * 构造方法: 初始化 元素成员变量
         * @param element
         */
        public Node(E element) {
            this.element = element;
        }

        /**
         *  构造方法,给 节点做初始化
         * @param prev 上一个节点的address
         * @param next 下一个节点的address
         * @param element 元素
         */
        public Node(Node<E> prev, E element,Node<E> next) {
            this.prev = prev;
            this.next = next;
            this.element = element;
        }
    }
}
